Рис. 4.9. Иллюстрация того, почему хребты вызывают сложности при восхождении к вершине. На хребет, возвышающийся слева направо, налагается решетка состояний (полужирные дуги), создавая последовательность локальных максимумов, которые не являются непосредственно связанными друг с другом. В каждом локальном максимуме все доступные действия направлены вниз

В каждом из этих случаев рассматриваемый алгоритм достигает такой точки, из которой не может осуществляться дальнейшее успешное продвижение. Начиная со случайно сформированного состояния с восемью ферзями, алгоритм поиска с восхождением к вершине по самому крутому подъему заходит в тупик в 86% случаях, решая только 14% экземпляров этой задачи. Но он работает очень быстро, выполняя в среднем только 4 этапа в случае успешного завершения и 3 этапа, когда заходит в тупик. Это не очень плохой результат для пространства состояний смиллионами состояний.

Алгоритм, приведенный в листинге 4.2, останавливается, достигнув плато, на котором наилучший преемник имеет такое же значение, как и в текущем состоянии. Имеет ли смысл продолжать движение, разрешив движение в сторону в надежде на то, что это плато в действительности представляет собой уступ, как показано на рис. 4.7? Ответ на этот вопрос обычно является положительным, но необходимо соблюдать осторожность. Если будет всегда разрешено движение в сторону, притом что движение вверх невозможно, могут возникать бесконечные циклы после того, как алгоритм достигнет плоского локального максимума, не являющегося уступом. Одно из широко применяемых решений состоит в том, что устанавливается предел количества допустимых последовательных движений в сторону. Например, можно разрешить, допустим, 100 последовательных движений в сторону в задаче с восемью ферзями. В результате этого относительное количество экземпляров задачи, решаемых с помощью восхождения к вершине, возрастает с 14 до 94%. Но за этот успех приходится платить: алгоритм в среднем выполняет приблизительно 21 этап при каждом успешном решении экземпляра задачи и 64 этапа при каждой неудаче.